package problem380;

import java.util.*;
//380. O(1) 时间插入、删除和获取随机元素
//https://leetcode.cn/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150
class RandomizedSet {

    List<Integer> list;
    Map<Integer, Integer> hash;
    Random random;

    public RandomizedSet() {
        list = new ArrayList<>();
        hash = new HashMap<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(hash.containsKey(val)) return false;
        int index = list.size();
        hash.put(val, index);
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(!hash.containsKey(val)) return false;
        int index = hash.get(val); //获取要删除元素在list中的下标
        //替换 
        hash.put(list.get(list.size()-1), index);
        hash.remove(val);
        list.set(index, list.get(list.size()-1));
        list.remove(list.size()-1);
        return true;
    }
    
    public int getRandom() {
        int index = random.nextInt(list.size());
        return list.get(index);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */